Using Euclids Extended Algorithm:
Calculate x and y in Bézout's Identity
using (97,921690)
For 2 numbers a and b and divisor d:
ax + by = d
a math | a | b math | b | d math | d | k math | k |
---|---|---|---|---|---|---|---|
Set to 1 | 1 | Set to 0 | 0 | 97 | |||
Set to 0 | 0 | Set to 1 | 1 | 921690 | Quotient of 97/921690 | 0 | |
1 - (0 x 0) | 1 | 0 - (0 x 1) | 0 | Remainder of 97/921690 | 97 | Quotient of 921690/97 | 9501 |
0 - (9501 x 1) | -9501 | 1 - (9501 x 0) | 1 | Remainder of 921690/97 | 93 | Quotient of 97/93 | 1 |
1 - (1 x -9501) | 9502 | 0 - (1 x 1) | -1 | Remainder of 97/93 | 4 | Quotient of 93/4 | 23 |
-9501 - (23 x 9502) | -228047 | 1 - (23 x -1) | 24 | Remainder of 93/4 | 1 | Quotient of 4/1 | 4 |
9502 - (4 x -228047) | 921690 | -1 - (4 x 24) | -97 | Remainder of 4/1 | 0 | Quotient of 1/0 | 0 |
a = -228047 and b = 24
ax + by = gcd(a,b)
97x + 921690y = gcd(97